---
id: unit3
title: 第三章  谓词逻辑
---



3.1 谓词的概念与表示

谓词用来指明个体的性质或个体之间的关系等，常用大写的英文字母P，Q，R，···来表示。由一个谓词、一些个体变量组成的表达式称为谓词变项或命题函数。

3.2 量词与合式公式

P（x）的全称量化是命题&quot;P（x）对x在其论域的所有值为真&quot;。符号VxP（x）表示P（x）的全称量化，其中V称为全称量词。

P（x）的存在量化是命题&quot;论域中存在一个元素x使P（x）为真&quot;。符号3xP（x）表示P（x）的存在量化，其中3称为存在量词。

［单选、填空、计算］辖域、约束变元、自由变元。

给定谓词合式公式A，其中一部分公式形式为VxB（x）或3xB（x），称量词V、3后面的x为指导变元也称为作用变元。称B（x）为相应量词的辖域（或作用域）。

在辖域中，x的一切出现称为约束出现。在B（x）中除去约束出现的其他变元的出现称为自由出现。

［单选、填空、计算］变元的改名和代入。

在谓词合式公式中，一个个体变元既可以是约束出现，又可以是自由出现，这很容易引起混淆。为了避免这些不必要的混淆，采用下面两个规则改变命题公式的写法：

（1）约束变元改名规则：将量词辖域中，量词的指导变元及其辖域中该变元的所有约束出现均改为本辖域中未曾出现过的个体变元，其余不变。

（2）自由变元代入规则：把公式中的某一自由变元，用该公式中没有出现的个体变元


·9

第3章谓词逻辑

符号替代，且要替换该自由变元在公式中的所有出现处。

3.3 谓词演算的等价式与蕴涵式

设论域元素为a1，a2，&quot;，an，则下列关系式成立：

(&quot;D)V V ·.. V (3D)V V (&#39;D)V(x)A

3xA(x)=A(a1) V A(a2) V··V A(an)。

给定任何两个谓词公式WffA和WIfB，设它们有共同的论域E，若对A和B的任一组个体变元进行赋值，所得命题的真值相同，则称谓词公式A和B在E上是等价的，并记作AB。

给定任意谓词公式WIIA，其论域为E，对于A的所有赋值WIfA都为真，则称WIIA在E上是有效的（或永真的）。如果在所有赋值下WffA都为假，则称WffA为不可满足的。如果至少在一种赋值下为真，则称该WffA是可满足的。

用谓词演算中的公式，代替命题演算公式中的变元，所得的公式即为等价式或蕴涵式。

［证明］谓词等值式与蕴涵式（下表）。

表谓词等值式和蕴涵式

| E23 | 3x(A(x) V B(x))→3xA(x)V3xB(x) |
| --- | --- |
| E24 | Vx(A(x)ΛB(x))VxA(x)^VxB(x) |
| E25 | -ヨxA(x)Vx~A(x) |
| E26 | -VxA(x)=3x~A(x) |
| E27 | Vx(AVB(x))AVVxB(x) |
| E28 | 3x(ΑΛB(x))AA3xB(x) |
| E29 | 3x(A(x) → B(x))VxA(x)→3xB(x) |
| E30 | VxA(x)→B3x(A(x)→B) |
| E31 | ヨxA(x)→BVx(A(x)→B) |
| E32 | A→VxB(x)Vx(A→B(x)) |
| E33 | A→3xB(x)3x(A→B(x)) |
| I17 | VxA(x)V VxB(x)Vx(A(x) V B(x)) |
| 118 | 3x(A(x)^B(x))\&gt;3xA(x)A3xB(x) |
|
 |
| 119 | 3xA(x)→VxB(x)Vx(A(x)→B(x)) |


3.4 前束范式

一个公式，如果量词均在全式的开头，它们的作用域延伸到整个公式的末尾，则该公式称为前束范式。

［计算］将谓词公式变换为前束范式的步骤。

（1）对不同辖域的同名变元进行换名（换名规则）。

（2）利用量词与否定联结词的关系，将否定联结词-深入到命题变元和谓词公式前面（量词转化规则）。

（3）利用等值式Vx（AVB（x））＝AVVxB（x）和ヨx（AΛB（x））→AA3xB（x），将量词移到全式最前面（量词前提规则）。

3.5 谓词演算的推理理论

［证明、综合应用］消去和添加量词的规则。

1．全称量词消去规则（简记为V一）

P是谓词，而c是论域中的任意一个个体，如果论域中全部个体都有P（x），那么对某个具体的个体c亦有P（x），即可得到结论P（c）。这条规则可表示为：

xP(x)

.P(c)

2．全称量词引入规则（简记为V＋）

如果能够证明对论域中任一个体c谓词P（c）都成立，则可得到VxP（x）为真。这称为全称量词引入规则。注意，这里的个体c必须是论域中的任意一个元素，而不能是某个特定的元素。这条规则可表示为：

P(x)

:.V.xP(x)

3．存在量词消去规则（简记为3一）

如果已知3xP（x）成立，则在论域中存在一个个体c使得P（c）为真。这里只知存在个体c，但不能选择任意的c，通常并不知道c的具体值。这条规则可表示为：

3xP(x)

:.P(c)

4．存在量词引人规则（简记为3＋）

如果已知论域中某个个体c使得P（c）为真，则可得出3xP（x）为真。这条规则可表示为：


第3章谓词逻辑

·11·

P(c) .3xP(x)

·12· 离散数学

